package sliding_window

/*
718.给两个整数数组nums1和nums2，返回 两个数组中【公共的】、【长度最长的】子数组的长度。
示例 1：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。
示例 2：
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5
*/

//暴力解法的伪代码：ans = 0
//for i in [0 .. A.length - 1]
//    for j in [0 .. B.length - 1]
//        k = 0
//        while (A[i+k] == B[j+k]) do   # and i+k < A.length etc.
//            k += 1
//        end while
//        ans = max(ans, k)
//    end for
//end for

//该暴力解法的最坏时间复杂度为 O(n^3)
//但通过观察该暴力解法，我们可以提出几个时间复杂度更优秀的解法。
//动态规划:
//暴力解法的过程中，我们发现最坏情况下对于任意 i 与 j ，A[i] 与 B[j] 比较了min(i+1,j+1) 次。这也是导致了该暴力解法时间复杂度过高的根本原因。
//不妨设 A 数组为 [1, 2, 3]，B 两数组为为 [1, 2, 4] ，那么在暴力解法中 A[2] 与 B[2] 被比较了三次。这三次比较分别是我们计算 A[0:] 与 B[0:] 最长公共前缀、 A[1:] 与 B[1:] 最长公共前缀以及 A[2:] 与 B[2:] 最长公共前缀时产生的。
//我们希望优化这一过程，使得任意一对 A[i] 和 B[j] 都只被比较一次。这样我们自然而然想到利用这一次的比较结果。
//如果 A[i] == B[j]，那么我们知道 A[i:] 与 B[j:] 的最长公共前缀为 A[i + 1:] 与 B[j + 1:] 的最长公共前缀的长度加一，否则我们知道 A[i:] 与 B[j:] 的最长公共前缀为零。
//这样我们就可以提出动态规划的解法：令 dp[i][j] 表示 A[i:] 和 B[j:] 的最长公共前缀，那么答案即为所有 dp[i][j] 中的最大值。
//如果 A[i] == B[j]，那么 dp[i][j] = dp[i + 1][j + 1] + 1，否则 dp[i][j] = 0。
//考虑到这里 dp[i][j] 的值从 dp[i + 1][j + 1] 转移得到，所以我们需要倒过来，首先计算 dp[len(A) - 1][len(B) - 1]，最后计算 dp[0][0]。

//时间复杂度： O(N×M)。
//空间复杂度： O(N×M)。
//N 表示数组 A 的长度，M 表示数组 B 的长度。
//空间复杂度还可以再优化，利用滚动数组可以优化到 O(min(N,M))。

func findLengthDP(nums1 []int, nums2 []int) int {
	n, m := len(nums1), len(nums2)
	//构建动态规划模型
	dp := make([][]int, n+1)
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, m+1)
	}
	ans := 0
	for i := n - 1; i >= 0; i-- {
		for j := m - 1; j >= 0; j-- {
			//填充值
			if nums1[i] == nums2[j] {
				dp[i][j] = dp[i+1][j+1] + 1
			} else {
				dp[i][j] = 0
			}
			if ans < dp[i][j] {
				ans = dp[i][j]
			}
		}
	}
	return ans
}

//滑动窗口:关键是对齐
//我们注意到之所以两位置会比较多次，是因为重复子数组在两个数组中的位置可能不同。以 A = [3, 6, 1, 2, 4], B = [7, 1, 2, 9] 为例，它们的最长重复子数组是 [1, 2]，在 A 与 B 中的开始位置不同。
//
//但如果我们知道了开始位置，我们就可以根据它们将 A 和 B 进行「对齐」，即：
//
//A = [3, 6, 1, 2, 4]
//B =    [7, 1, 2, 9]
//           ↑  ↑
//此时，最长重复子数组在 A 和 B 中的开始位置相同，我们就可以对这两个数组进行一次遍历，得到子数组的长度，伪代码如下：
//
//ans = 0
//len = min(A.length, B.length)
//k = 0
//for i in [0 .. len - 1] do
//    if (A[i] == B[i]) then
//        k = k + 1
//    else
//        k = 0
//    end if
//    ans = max(ans, k)
//end for
//
//注意这里指定了 A[i] 对齐 B[i]，在实际代码实现中会通过指定初始位置 addA 与 addB 的方式来对齐，因此表达式会略有差别。
//
//我们可以枚举 A 和 B 所有的对齐方式。对齐的方式有两类：第一类为 A 不变，B 的首元素与 A 中的某个元素对齐；第二类为 B 不变，A 的首元素与 B 中的某个元素对齐。
//对于每一种对齐方式，我们计算它们相对位置相同的重复子数组即可。

//时间复杂度： O((N+M)×min(N,M))
//空间复杂度： O(1)
//N 表示数组 A 的长度，M 表示数组 B 的长度。

func findLengthSW(nums1 []int, nums2 []int) int {
	n, m := len(nums1), len(nums2)
	ret := 0

	//进行对齐操作
	for i := 0; i < n; i++ {
		l := min(m, n-i) //逐步移动
		//对齐后，进行比较
		maxLen := maxLength(nums1, nums2, i, 0, l)
		ret = max(ret, maxLen)
	}

	for i := 0; i < m; i++ {
		l := min(n, m-i)
		//对齐后，进行比较
		maxLen := maxLength(nums1, nums2, 0, i, l)
		ret = max(ret, maxLen)
	}
	return ret
}

// addA 切片A的起始位置
// addB 切片B的起始位置
// len 对齐需要移动的距离
func maxLength(A, B []int, addA, addB, len int) int {
	ret, k := 0, 0
	for i := 0; i < len; i++ {
		if A[addA+i] == B[addB+i] {
			k++
		} else {
			k = 0
		}
		ret = max(ret, k)
	}
	return ret
}
